package BinaryTree;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-07-22
 * Time: 20:49
 */

/**
 * 从中序与后序遍历序列构造二叉树

 * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
 *
 *
 *
 * 示例 1:
 *
 *
 * 输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
 * 输出：[3,9,20,null,null,15,7]
 * 示例 2:
 *
 * 输入：inorder = [-1], postorder = [-1]
 * 输出：[-1]
 *
 *
 * 提示:
 *
 * 1 <= inorder.length <= 3000
 */
public class BinaryExercise3 {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postorIndex = postorder.length-1;
        return buildTreeChild(inorder, postorder,0,inorder.length-1);
    }


    public int postorIndex;
    public TreeNode buildTreeChild(int[] inorder , int[] postorder,int inbegin, int inend) {

        //没有左树或者右树
        if(inbegin > inend) {
            return null;
        }

        //new一个根节点
        TreeNode root = new TreeNode(postorder[postorIndex]);

        //在中序遍历中从，前序遍历那里找到，代表所有子树的 根节点
        int rootIndex = findVal(inorder,inbegin,inend, postorder[postorIndex]);

        //postorIndex，要改为全局变量，左右每次递归是，才不会重置为0
        postorIndex--;//rootInde用完才加加；

        //递归每一个创建右左子树

        root.right = buildTreeChild(inorder,postorder,rootIndex+1,inend);
        root.left = buildTreeChild(inorder,postorder,inbegin,rootIndex-1);

        return root;
    }

    private int findVal(int[] inorder,int inbegin, int inend,int val) {
        for(int i = inbegin; i<=inend; i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }


}
